/* Copyright 2011 Tobias Marschall, Email: tm@cwi.nl 
 * 
 * This file is part of string-cover.
 *
 * string-cover is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * string-cover is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with string-cover.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef BRANCHINGRULE_H_
#define BRANCHINGRULE_H_

#include <iostream>
#include <limits>
#include "ProblemInstance.h"
#include "BranchingRule.h"

enum branching_rule_t { LOWER_BOUND, BEST_SOLUTION };

template <typename Queue>
class BranchingRule {
private:
	const ProblemInstance& instance;
	branching_rule_t rule;
public:
	BranchingRule(const ProblemInstance& instance, branching_rule_t rule) : instance(instance), rule(rule) {};
	virtual ~BranchingRule() {};
	/** Makes a branching decision and adds the newly created nodes to the given queue.
	 *  @param substring_weight_sums Array of _relative_ weights of used intervals, i.e.
	 *                               for each substring the sum of multipliers of used intervals
	 *                               (normalized to one). */
	virtual void branch(Queue& queue, const BranchAndBoundNode& node, double local_lower_bound, const Solution& solution, const double* substring_weight_sums) const;
};

template<typename Queue>
void BranchingRule<Queue>::branch(Queue& queue, const BranchAndBoundNode& node, double local_lower_bound, const Solution& solution, const double* substring_weight_sums) const {
#ifdef DEBUG
	std::cout << "Branching at node:"<< node << std::endl;
#endif
	// search for substring with multiplier_sum / weight most closely to 0.5
	double best_abs_diff = std::numeric_limits<double>::infinity();
	double best_ratio = -1.0;
	size_t best_index = 0;
	const SubstringStore& substrings = instance.getSubstrings();
	for (size_t i=0; i<substrings.size(); ++i) {
#ifdef DEBUG
		if (substring_weight_sums[i]>0.0) {
			std::cout << "  " << substrings.getSubstring(i) << ": " << substring_weight_sums[i] << std::endl;
		}
#endif
		if (node.isForbidden(i) || node.isIncluded(i)) continue;
		double abs_diff = fabs(0.5-substring_weight_sums[i]);
		if (abs_diff<best_abs_diff) {
			// std::cout << "  new best abs diff: "<< substrings.getSubstring(i)<<":" << abs_diff << ", ratio: "<< ratio<< std::endl;
			best_abs_diff = abs_diff;
			best_ratio = substring_weight_sums[i];
			best_index = i;
		}
	}
	if (best_abs_diff < std::numeric_limits<double>::infinity()) {
		BranchAndBoundNode* child0 = new BranchAndBoundNode(node);
		BranchAndBoundNode* child1 = new BranchAndBoundNode(node);
		child0->includeSubstring(best_index);
		child1->forbidSubstring(best_index);
		if (rule==BEST_SOLUTION) {
			double score = solution.getScore();
			if (instance.hasIntegerWeights()) {
				child0->setPriority(score+1.0-best_ratio);
				child1->setPriority(score+best_ratio);
			} else {
				child0->setPriority(score);
				child1->setPriority(score);
			}
		} else if (rule==LOWER_BOUND) {
			child0->setPriority(local_lower_bound);
			child1->setPriority(local_lower_bound);
		} else { assert(false); }
#ifdef DEBUG
		std::cout << "Branching at substring " << substrings.getSubstring(best_index) << std::endl;
#endif
		queue.push(child0);
		queue.push(child1);
	}
}

#endif /* BRANCHINGRULE_H_ */
